This application is directed to a system and method for use in a manufacturing or production planning environment, and more particularly to generating and using a tool which employs network flow modeling to either determine an exact optimal value or optimistic estimate of an operational parameter for the manufacturing or production planning environment.
Existing methods for analyzing manufacturing systems can require invoking an expensive combinatorial planner/scheduler multiple times in order to estimate throughput under many different conditions.
A typical manufacturing environment may be represented as a network of transports linking multiple components, as shown in FIG. 1. A manufacturing environment may have anywhere from a few to a several hundred components (e.g. machines) and paths (e.g., transports). Unfinished commodities or material may enter the environment from multiple sources and completed jobs can exit at multiple destinations. In the simplified schematic of FIG. 1, Sources 1 and 2 provide materials to Machine 1 and Machine 2, which interface with Machine 3 and Machine 4 as well as Destinations 1 and 2. The to-be-disclosed system is also able to handle the scenario of producing multiple products, each with its own sequence of operations.
From a planning perspective, jobs can move through the environment as illustrated in FIG. 2. A job request specifies a desired final configuration, which may be achievable by several different sequences of actions
One area which addresses scheduling/planning is stochastic processing networks. In this area, the question being asked is, if you have a buffer on the input to each machine, by what manner is material to be routed through the system to minimize the length of the backlog in the buffers, and how can the throughput of the network be maximized. Stochastic methods use optimization techniques such as, Markov decision processes, approximate dynamic programming, Brownian motion approximations, etc. to compute routing policies. An issue with the stochastic approach is that it makes the assumption that it is not possible to accurately time how long a certain process will take. In view of its presumptions, stochastic techniques will include modeling the processing times of components as Markov random variables. In other words, it will be assumed that each time a component is processed by a machine, it will take a slightly different amount of time, that follows some probability distribution. However in real manufacturing systems, processing time estimates can be highly accurate, and are not necessarily random variables.
The assumptions of the stochastic based methods add much complexity to the stochastic-type planners. One of the more difficult issues in stochastic analysis is that when a stochastic scheduling/planning system is implemented, transients (start-up transients and ramp-down transients) exist, and a great deal of effort and processing is needed to quantify the transients. These transients exist due to the non steady-state environment in which the planners function.
Another area of planning is related to flow-based models for manufacturing systems, as discussed in the article, “Applying the Network Flow Model to Evaluate an FMC's Throughput”, Wang et al., Int. J. Prod. Res., 2002, Vol. 40, No. 3, 525-536. The described system employs nodes and links to create a multi-commodity network flow, which uses fixed routes. The system discussed in this paper does not address a situation where components of the system are actually physically distributed, or where there is a need to handle re-entrant lines (i.e. a cycle flow through the system). In fact, the paper states that, “[o]wing to the inherent limitations of a maximum flow network, a cycle should not be formed in the network. So care must be taken that multiple alternative routing will not result in a cycle while using this model.” Therefore the paper explicitly rules out cycles, and re-entrant flows.
Yet another line of research on deterministic methods for scheduling has been reported by Bertsimas, Gamarnik, and Sethurman in the article, From Fluid Relaxations to Practical Algorithms for Job Shop Scheduling: The Holding Cost Objective, Operations Research, 51, 2003, and the references therein. This work addresses make-span type objectives (holding cost, etc.) but does not produce a steady state analysis. It also does not address the case with arbitrary routing, where there are multiple machines of the same type. An earlier work by the same authors, cited in the above article, addresses routing, but only in a very restricted packet-routing setting, where each packet has a single source and single destination, and does not allow for a sequence of machine types (destinations), each of which has several possible locations in the network.
The above-described planning techniques, and other existing techniques each have various drawbacks. For example, bound/branch (state-space) searching is often used to solve planning/scheduling problems. However, such problems solved by such techniques are known to grow exponentially as the problems become more complex, resulting in the searches used to solve these problems, themselves becoming very complex, requiring large amounts of processing power and time to complete the searches. Additionally, existing planner/schedulers are normally optimized in a job-at-a-time process. This has certain drawbacks, and in fact may not be implementable if one is attempting to investigate optimal steady state performance. In view of these drawbacks, it is considered that improvements in developing a tool which can quickly obtain either an exact or optimistic estimate of the system's optimal behavior has benefits not obtained by the existing systems